package leetCode.array_and_string;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 功能：合并区间
 * 作者：lc
 * 日期：2025/2/14 23:57
 */
public class Main56 {
    /**
     *
     * 整体思路：
     * 通过左端进行排序，然后遍历合并
     * 合并细节： 1.如果ans为空直接添加
     *          2.如果不为空（size>0）
     *          2.1如果合并的区间的r大于等于l,则合并，合并区间的左边界为ans左边界，右边界为max值
     *          2.2.如果合并的区间的r小于l,则直接添加
     * 这里为什么用ArrayList主要是因为不需要关心数组的长度，即动态管理结果集的不确定性
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        // 1.排序，保证左边界从小到大
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        ArrayList<int[]> ans = new ArrayList<>();
        for (int[] interval : intervals) {
            int size = ans.size();
            if(size>0&&ans.get(size-1)[1] >= interval[0]) {
                 ans.get(size-1)[1] = Math.max(ans.get(size - 1)[1], interval[1]);
            }else {
                ans.add(interval);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
